function path = A_star_search(map,MAX_X,MAX_Y)
%%
%This part is about map/obstacle/and other settings
    %pre-process the grid map, add offset
    size_map = size(map,1);
    Y_offset = 0;
    X_offset = 0;
    
    %Define the 2D grid map array.
    %Obstacle=-1, Target = 0, Start=1
    MAP=2*(ones(MAX_X,MAX_Y));
    
    %Initialize MAP with location of the target
    xval=floor(map(size_map, 1)) + X_offset;
    yval=floor(map(size_map, 2)) + Y_offset;
    xTarget=xval;
    yTarget=yval;
    MAP(xval,yval)=0;
    
    %Initialize MAP with location of the obstacle
    for i = 2: size_map-1
        xval=floor(map(i, 1)) + X_offset;
        yval=floor(map(i, 2)) + Y_offset;
        MAP(xval,yval)=-1;
    end 
    
    %Initialize MAP with location of the start point
    xval=floor(map(1, 1)) + X_offset;
    yval=floor(map(1, 2)) + Y_offset;
    xStart=xval;
    yStart=yval;
    MAP(xval,yval)=1;

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %LISTS USED FOR ALGORITHM
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %OPEN LIST STRUCTURE
    %--------------------------------------------------------------------------
    %IS ON LIST 1/0 |X val |Y val |Parent X val |Parent Y val |h(n) |g(n)|f(n)|
    %--------------------------------------------------------------------------
    OPEN=[];
    %CLOSED LIST STRUCTURE
    %--------------
    %X val | Y val |
    %--------------
    % CLOSED=zeros(MAX_VAL,2);
    CLOSED=[];

    %Put all obstacles on the Closed list
    k=1;%Dummy counter
    for i=1:MAX_X
        for j=1:MAX_Y
            if(MAP(i,j) == -1)
                CLOSED(k,1)=i;
                CLOSED(k,2)=j;
                k=k+1;
            end
        end
    end
    CLOSED_COUNT=size(CLOSED,1);
    %set the starting node as the first node
    xNode=xval; 
    yNode=yval;
    OPEN_COUNT=1;
    goal_distance=distance(xNode,yNode,xTarget,yTarget);
    path_cost=0;
    OPEN(OPEN_COUNT,:)=insert_open(xNode,yNode,xNode,yNode,goal_distance,path_cost,goal_distance);
    OPEN(OPEN_COUNT,1)=1; % note: change here
    CLOSED_COUNT=CLOSED_COUNT+1;
    CLOSED(CLOSED_COUNT,1)=xNode;
    CLOSED(CLOSED_COUNT,2)=yNode;
    NoPath=1;

%%
%This part is your homework
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% START ALGORITHM
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    while(1) %you have to dicide the Conditions for while loop exit 
        if sum(OPEN(:,1))==0
            break;
        end
        % pop the node "n" with the lowest f(n)
        i_index = min_fn(OPEN, length(OPEN(:,1)), xTarget, yTarget);
        
        xNode_expanded = OPEN(i_index,2);
        yNode_expanded = OPEN(i_index,3);
        gNode_expanded = OPEN(i_index,7);
        OPEN(i_index,1) = 0;
        
        CLOSED_COUNT = CLOSED_COUNT+1;
        CLOSED(CLOSED_COUNT,1) = xNode_expanded;
        CLOSED(CLOSED_COUNT,2) = yNode_expanded;
        
        if xNode_expanded == xTarget && yNode_expanded == yTarget
            NoPath = 0;
            break;
        end
        
        exp_array = expand_array(xNode_expanded, yNode_expanded, gNode_expanded, xTarget, yTarget, CLOSED, MAX_X, MAX_Y);
        
        if ~isempty(exp_array)
            for i=1:1:length(exp_array(:,1))
                xNode = exp_array(i,1);
                yNode = exp_array(i,2);
                n_inx = node_index(OPEN, xNode, yNode);
                if isempty(n_inx)
                    OPEN_COUNT = OPEN_COUNT+1;
                    hn = exp_array(i,3);
                    gn = exp_array(i,4);
                    fn = exp_array(i,5);
                    OPEN(OPEN_COUNT,:) = insert_open(xNode, yNode, xNode_expanded, yNode_expanded, hn, gn, fn);
                else
                    pre_gn = OPEN(n_inx,7);
                    if pre_gn > exp_array(i,4)
                        OPEN(n_inx,4) = xNode_expanded;
                        OPEN(n_inx,5) = yNode_expanded;
                        OPEN(n_inx,7) = exp_array(i,4);
                        OPEN(n_inx,8) = exp_array(i,5);
                    end
                end
            end
        end      
     %
     %finish the while loop
     %
     
    end %End of While Loop
    
    %Once algorithm has run The optimal path is generated by starting of at the
    %last node(if it is the target node) and then identifying its parent node
    %until it reaches the start node.This is the optimal path
    
    %
    %How to get the optimal path after A_star search?
    %please finish it
    %
    
   path = [];
   if(~NoPath)
       parent_index = node_index(OPEN,xTarget,yTarget);
       for i=1:size(OPEN,1)
           path(end+1,:) = [OPEN(parent_index,2), OPEN(parent_index,3)];
           if(OPEN(parent_index,2)==xStart && OPEN(parent_index,3)==yStart)
               break;
           end
           parent_x = OPEN(parent_index,4);
           parent_y = OPEN(parent_index,5);
           parent_index = node_index(OPEN,parent_x,parent_y);
       end
   end
   path = flip(path,1);
end
